package subjectlist;

import java.util.Arrays;

public class N如何找到由其他单词组成的最长单词 {

    /**
     * 题目描述：
     * 给定一个字符串数组，找出数组中最长的字符串，使其能由数组中其他的字符串组成。
     * 例如，给定字符串数组{“test”，“tester”，“testertest”，“testing”，“apple”，“seattle”，“banana”，“batting”，“ngcat”，“batti”，“bat”，“testingtester”，“testbattingcat”}。
     * 满足题目要求的字符串为“testbattingcat”，
     * 因为这个字符串可以由数组中的字符串“test”“batti”和“ngcat”组成
     */

    /**
     * 分析与解答：既然题目要求找最长的字符串，那么可以采用贪心的方法，
     * 首先对字符串由大到小进行排序，从最长的字符串开始查找，如果能由其他字符串组成，就是满足题目要求的字符串。
     * 接下来就需要考虑如何判断一个字符串能否由数组中其他的字符串组成，
     * 主要思路为：找出字符串的所有可能的前缀，判断这个前缀是否在字符数组中。
     * 如果在，那么用相同的方法递归地判断除去前缀后的子串是否能由数组中其他的子串组成
     *
     * 以题目中给的例子为例，
     * 首先对数组进行排序，排序后的结果：
     * {“testbattingcat”，“testingtester”，“testertest”，“testing”，“seattle”，“batting”，“tester”，“banana”，“apple”，“ngcat”，“batti”，“test”，“bat”}。首先取“testbattingcat”进行判断，
     * 具体步骤如下：
     * 1）分别取它的前缀“t”“te”“tes”都不在字符数组中，“test”在字符数组中。
     * 2）接着用相同的方法递归地判断剩余的子串“battingcat”。同理，“b”“ba”都不在字符数组中，“bat”在字符数组中。
     * 3）接着判断“tingcat”，通过判断发现“tingcat”不能由字符数组中其他字符组成。
     * 因此，回到上一个递归调用的子串接着取字符串的前缀进行判断。
     * 4）回到上一个递归调用，待判断的字符串为“battingcat”，当前比较到的前缀为“bat”，接着取其他可能的前缀“batt”“battt”都不在字符数组中，“battti”在字符数组中。接着判断剩余子串“ngcat”。5）通过比较发现“ngcat”在字符数组中。因此，能由其他字符组成的最长字符串为“testbattingcat”
     */

    //判断字符串str是否在字符串数组中
    boolean find(String[] strArray,String str){
        for (int i = 0; i < strArray.length; i++) {
            if (str.equals(strArray[i])) {
                return true;
            }
        }
        return false;
    }

    private boolean isContain(String[] strArray,String word,int length){
        int len=word.length();
        //递归的结束条件，当字符串长度为0时，说明字符串已经遍历完了
        if (len == 0) {
            return true;
        }
        //循环取字符串的所有前缀
        for (int i = 1; i <=len; ++i) {
            //取到的子串为自己
            if(i==length){
                return false;
            }
            String str=word.substring(0,i);
            if(find(strArray,str)){
                //查找完字符串的前缀后，递归判断后面的子串能否由其他单词组成
                if(isContain(strArray,word.substring(i),length)){
                    return true;
                }
            }
        }
        return false;
    }

    //找出能由数组中其他字符串组成的最长字符串
    public String getLongestStr(String[] strArray){
        //对字符串由大到小排序
        Arrays.sort(strArray);
        //贪心地从最长的字符串开始判断
        for (int i = 0; i < strArray.length; i++) {
            if(isContain(strArray,strArray[i],strArray[i].length())){
                return strArray[i];
            }
        }
        return null;
    }

    public static void main(String[] args) {
        String strArray[]={
                "test","tester","testertest","testing","apple","seattle","banana","batting",
                "ngcat","batti","bat","testingtester","testbattingcat"};
        N如何找到由其他单词组成的最长单词 lw=new N如何找到由其他单词组成的最长单词();
        String longestStr = lw.getLongestStr(strArray);
        if(longestStr!=null){
            System.out.println("最长的字符串为："+longestStr);
        }else {
            System.out.println("不存在这样的字符串");
        }
    }
}
